一、Graph CNN [2016]

《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》

1. 卷积神经网络提供了一种有效的架构，可以在大规模的、高维的数据集中抽取非常有意义的统计模式（statistical pattern）。CNN 学习局部静态结构（ local stationary structure ）并将它们组合成多尺度的（ multi-scale）、分层（hierarchical）的模式，并导致了图像识别、视频识别、声音识别等任务的突破。准确地说，CNN 通过揭示跨数据域（data domain）共享的局部特征来抽取输入数据（或输入信号）的局部平稳性（local stationarity ）。这些相似的特征通过从数据中学到的局部卷积滤波器（localized convolutional filter ）（或局部卷积核 localized convolutional kernel）来识别。卷积滤波器是平移不变（translation-invariant）的，这意味着它们能够独立于空间位置来识别相同的特征（identical feature）。局部核（localized kernel） （或紧凑支持的滤波器compactly supported filter）指的是独立于输入数据大小并抽取局部特征的滤波器，它的支持度（ support ）大小可以远小于输入大小。

   社交网络上的用户数据、电信网络上的日志数据、或 word embedding 上的文本文档，它们都是不规则数据的重要例子，这些数据可以用图 （graph） 来构造。图是异质 pairwise 关系的通用表达（universal representation）。图可以编码复杂的几何结构，并且可以使用强大的数学工具进行研究，如谱图理论（spectral graph theory）。

   将 CNN 推广到图并不简单，因为卷积算子和池化算子仅针对规则网格（regular grid）才有定义。这使得 CNN 的扩展在理论上和实现上都具有挑战性。将 CNN 推广到图的主要瓶颈（也是论文 《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》的主要目标之一），是定义可以有效评估和学习的局部图滤波器localized graph filter 。准确地说，论文 《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》的主要贡献如下：

   • 谱公式 （spectral formulation）：基于图信号处理（ graph signal processing: GSP ）中已有的工具，论文建立了图上 CNN 的谱图（spectral graph）理论公式。

   • 严格局部的滤波器：可以证明，论文提出的谱滤波器（ spectral filter ）严格限定在半径为 $K$$K$ 的球中，即从中心顶点的 K hops 。这是对 《Spectral Networks and Deep Locally Connected Networks on Graphs》 的增强。

   • 低的计算复杂度：论文提出的滤波器的 evaluation 复杂度与滤波器尺寸 $K$$K$ 、图的边数 $|\mathcal{E}|$$|\mathcal E|$ 成正比。重要的是，由于大多数现实世界的图都是高度稀疏的，因此有 $|\mathcal{E}|\ll n^2$$|\mathcal E|\ll n^2$ 以及 $|\mathcal{E}|=kn$$|\mathcal E|=kn$ ，其中 $n$$n$ 为图的顶点数，$k$$k$ 为图中顶点的平均 degree。这使得计算复杂度与输入数据大小 $n$$n$ 成线性关系。

     此外，论文的方法完全避免了傅里叶基（ Fourier basis），因此避免了计算傅里叶基所需要的特征分解 （eigenvalue decomposition）所需的计算量，也避免了存储傅里叶基的内存需求（一个 $n\times n$$n\times n$ 的矩阵）。这在 GPU 内存有限时尤其重要。除了输入数据之外，论文的方法只需要存储拉普拉斯算子，它是一个包含 $|\mathcal{E}|$$|\mathcal E|$ 个非零值的稀疏矩阵。

   • 高效的池化：论文提出了一种有效的、图上的池化策略，该策略在将顶点重排为二叉树结构之后，采用类似于一维信号的池化。

   • 实验结果：论文进行了多个实验，最终表明所提出的公式是：一个有效的模型、计算效率高、在准确性和复杂性上都优于 《Spectral Networks and Deep Locally Connected Networks on Graphs》 中介绍的 spectral graph CNN 。

     论文还表明，所提出的图公式在 MNIST上的表现与经典 CNN 相似，并研究了各种图构造（graph construction）对于性能的影响。

2. 相关工作：

   • 图信号处理（ graph signal processing: GSP）：GSP 的新兴领域旨在弥合信号处理和谱图理论之间的 gap ，是图论（graph theory）和谐波分析（harmonic analysis）之间的融合。一个目标是将信号的基本分析操作从规则网格推广到不规则的图结构。诸如卷积、平移、滤波 （filtering）、膨胀 （dilatation）、调制 （modulation）、降采样（downsampling）等等网格上的标准操作不会直接扩展到图，因此需要新的数学定义，同时保持原有的直观概念。在这种情况下，已有工作重新审视了图上小波算子（wavelet operator）的构建，并提出了在图上执行 mutli-scale pyramid transform 。也有一些工作重新定义了图上的不确定性原理，并表明虽然可能会丢失直观的概念，但是可以导出增强的局部性准则 （localization principle）。

   • 非欧几里得（Non-Euclidean）域的 CNN：图神经网络框架《The Graph Neural Network Model》（在 《Gated Graph Sequence Neural Networks》 中被简化）旨在通过 RNN 将每个节点嵌入到一个欧氏空间，并将这些 embedding 用作节点/图的分类/回归的特征。

     一些工作引入了构建局部感受野（local receptive field ）的概念从而减少学习参数的数量。这个想法是基于相似性度量将特征组合在一起，例如在两个连续层之间选择有限数量的连接。虽然该模型利用局部性假设（locality assumption）减少了参数的数量，但是它并没有尝试利用任何平稳性，即没有权重共享策略。《Spectral Networks and Deep Locally Connected Networks on Graphs》 的作者在他们的 graph CNN 的 spatial formulation 中使用了这个想法。他们使用加权图来定义局部邻域，并为池化操作计算图的多尺度聚类（multiscale clustering）。然而，在空域构造（spatial construction ）中引入权重共享具有挑战性，因为当缺少 problem-specific ordering （如空间顺序、时间顺序等等）时，它需要选择（select ）并对邻域内的节点进行排序。

     《Geodesic convolutional neural networks on riemannian manifolds》 中提出了 CNN 到 3D-mesh 的空间推广，其中 3D-mesh 是一类平滑的、低维的非欧氏空间。作者使用测地线极坐标（geodesic polar coordinate ）来定义 mesh patch 上的卷积，并定制了一个深度学习架构从而允许在不同的流形（manifold）之间进行比较。他们对 3D 形状识别获得了 SOTA 结果。

     第一个谱公式由 《Spectral Networks and Deep Locally Connected Networks on Graphs》 提出，它将滤波器定义为：$g_{\theta }(\mathbf{\Lambda })=\mathbf{B}\theta$$g_\theta(\mathbf\Lambda) = \mathbf B\theta$，其中 $\mathbf{B}\in {\mathbb{R}}^{n\times K}$$\mathbf B\in \mathbb R^{n\times K}$ 为三次 $B$$B$ 样条基，参数 $\theta \in {\mathbb{R}}^K$$\theta\in \mathbb R^K$ 为控制点（control point）向量。他们后来提出了一种从数据中学习图结构的策略，并将该模型应用于图像识别、文本分类、生物信息学（《Deep Convolutional Networks on Graph-Structured Data》）。然而，由于需要乘以图傅里叶基 $\mathbf{U}\in {\mathbb{R}}^{n\times n}$$\mathbf U\in \mathbb R^{n\times n}$ ，因此这种方法没办法 scale 。此外，由于它们依赖于傅里叶域中的平滑性（smoothness）（即，通过样条参数化得到）来实现空间域的局部性，因此他们的模型无法提供精确的控制从而使得 kernel 支持局部性，而这对于学习局部的滤波器至关重要。我们的技术利用了这项工作，并展示了如何克服这些限制以及其它限制。

1.1 模型

1. 将卷积推广到图上需要考虑三个问题：如何在图上设计满足空域局部性的卷积核、如何执行图的粗化（graph coarsening）（即，将相似顶点聚合在一起）、如何执行图池化操作。

1.1.1 快速的局部性的谱滤波器

1. 定义卷积滤波器有两种策略，可以从空间方法（spatial approach）来定义，也可以从谱方法（spectral approach）来定义。

   • 通过构造（ construction），空间方法可以通过有限大小的 kernel 提供 filter localization 。然而，从空间角度来看，图上的平移没有唯一的数学定义。

   • 另一方面，谱方法通过在谱域（spectral domain）实现的 Kronecker delta 卷积在图上提供了一个定义明确的局部性算子（ localization operator ）。然而，在谱域定义的滤波器不是天然局部化的，并且由于和图傅里叶基乘法的计算复杂度为 $O(n^2)$$O(n^2)$，因此傅里叶变换的成本很高。

     然而，通过对滤波器参数化（filter parametrization）的特殊选择，我们可以克服这两个限制（即，滤波器的天然局部化，以及计算复杂度）。

2. 图傅里叶变换（Graph Fourier Transform）：给定无向图 $G=(\mathcal{V},\mathcal{E},\mathbf{W})$$G=(\mathcal V,\mathcal E,\mathbf W)$，其中 $\mathcal{V}$$\mathcal V$ 为顶点集合，$n=|\mathcal{V}|$$n=|\mathcal V|$ 为顶点数量，$\mathcal{E}$$\mathcal E$ 为边集合， $\mathbf{W}\in {\mathbb{R}}^{n\times n}$$\mathbf W\in \mathbb R^{n\times n}$ 为一个加权的邻接矩阵，$W_{i,j}$$W_{i,j}$ 编码了两个顶点 $i$$i$ 和 $j$$j$ 之间的连接权重。

   $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\mathbf{\vec x}\in \mathbb R^n$ 是定义在图中节点上的信号，其中 $x_i\in \mathbb{R}$$x_i\in \mathbb R$ 为第 $i$$i$ 个节点上的取值。谱图分析（spectral graph analysis ）中最基础的算子是图拉普拉斯算子，combinatorial Laplacian 定义为 $\mathbf{L}=\mathbf{D}-\mathbf{W}\in {\mathbb{R}}^{n\times n}$$\mathbf L = \mathbf D - \mathbf W\in \mathbb R^{n\times n}$ ，normalized Laplacian 定义为 $\mathbf{L}={\mathbf{I}}_n-{\mathbf{D}}^{-1/2}\mathbf{W}{\mathbf{D}}^{-1/2}$$\mathbf L = \mathbf I_n- \mathbf D^{-1/2}\mathbf W \mathbf D^{-1/2}$，其中 $\mathbf{D}$$\mathbf D$ 为degree 矩阵（一个对角矩阵）并且 $D_{i,i}=\sum _j{W}_{i,j}$$D_{i,i} = \sum_{j} W_{i,j}$ ， ${\mathbf{I}}_n\in {\mathbb{R}}^{n\times n}$$\mathbf I_n\in \mathbb R^{n\times n}$ 为一个单位矩阵。

   论文并没有提到是用哪个拉普拉斯矩阵，读者猜测用的是任意一个都可以，因为后续公式推导对两种类型的拉普拉斯矩阵都成立。

   由于 $\mathbf{L}$$\mathbf L$ 是一个实对称半正定矩阵，因此它有一组完全的正交特征向量 ${\left\{{\overrightarrow{\mathbf{u}}}_l\right\}}_{l=0}^{n-1}\in {\mathbb{R}}^n$$\left\{\mathbf{\vec u}_l\right\}_{l=0}^{n-1}\in \mathbb R^n$ （称作图傅里叶模式 graph Fourier mode ），以及与这些特征向量相关的有序实数非负特征值 $\{{\lambda }_l{\}}_{l=0}^{n-1}\in \mathbb{R}$$\{\lambda_l\}_{l=0}^{n-1}\in \mathbb R$ （称作图的频率 graph frequency）。图拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 被傅里叶基Fourier basis $\mathbf{U}=[{\overrightarrow{\mathbf{u}}}_0,\cdots ,{\overrightarrow{\mathbf{u}}}_{n-1}]\in {\mathbb{R}}^{n\times n}$$\mathbf U=\left[\mathbf{\vec u}_0,\cdots,\mathbf{\vec u}_{n-1}\right]\in \mathbb R^{n\times n}$ 所对角化，使得 $\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$\mathbf L = \mathbf U\mathbf\Lambda\mathbf U^\top$，其中 $\mathbf{\Lambda }=\text{diag}([{\lambda }_0,\cdots ,{\lambda }_{n-1}])\in {\mathbb{R}}^{n\times n}$$\mathbf\Lambda = \text{diag}([\lambda_0,\cdots,\lambda_{n-1}])\in \mathbb R^{n\times n}$ ，$\mathbf{U}$$\mathbf U$ 的第 $l$$l$ 列为特征向量 ${\overrightarrow{\mathbf{u}}}_l$$\mathbf{\vec u}_l$ 。

   傅里叶变换将信号 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\mathbf{\vec x}\in \mathbb R^n$ 转换为 $\widehat{\overrightarrow{\mathbf{x}}}={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\hat{\mathbf{\vec x}} = \mathbf U^\top \mathbf{\vec x}\in \mathbb R^n$ ，傅里叶逆变换为 $\overrightarrow{\mathbf{x}}=\mathbf{U}\widehat{\overrightarrow{\mathbf{x}}}$$\mathbf{\vec x} = \mathbf U\hat{\mathbf{\vec x}}$ 。与欧氏空间一样，傅里叶变换能够定制化基本操作，如滤波 filtering 。

3. 图信号的谱域滤波（spectral filtering）：由于我们无法在顶点域（vertex domain ）中表达有意义的平移算子（translation operator），因此图上的卷积算子 ${\ast }_{\mathcal{G}}$$*_\mathcal G$ 定义在傅里叶域（Fourier domain），即：

   $${\overrightarrow{\mathbf{x}}}_1{\ast }_{\mathcal{G}}{\overrightarrow{\mathbf{x}}}_2=\mathbf{U}(\left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_1\right)\odot \left({\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_2\right))$$

   其中：$\odot$$\odot$ 是逐元素的 Hadamard 乘法，${\overrightarrow{\mathbf{x}}}_1,{\overrightarrow{\mathbf{x}}}_2\in {\mathbb{R}}^n$$\mathbf{\vec x}_1,\mathbf{\vec x}_2\in\mathbb R^n$ 都是图上定义的两个信号。

   因此，图上的信号 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 被 $g_{\theta }$$g_\theta$ 滤波为：

   $$\overrightarrow{\mathbf{y}}=g_{\theta }(\mathbf{L})\overrightarrow{\mathbf{x}}=g_{\theta }\left(\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}\right)\overrightarrow{\mathbf{x}}=\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   non-parametric filter （即参数都是自由的滤波器）定义为：

   $$\begin{array}{c}{g}_{\theta }(\mathbf{\Lambda })=\text{diag}\left(\overrightarrow{\theta }\right)=\left[\begin{array}{cccc}{\theta }_1& 0& \cdots & 0\\ 0& {\theta }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\theta }_n\end{array}\right]\end{array}$$

   其中参数 $\overrightarrow{\theta }=({\theta }_1,\cdots ,{\theta }_n)\in {\mathbb{R}}^n$$\vec\theta=(\theta_1,\cdots,\theta_n)\in \mathbb R^n$ 为待学习的傅里叶系数Fourier coefficient 组成的向量。

4. 用于局部滤波器（localized filter）的多项式参数化：然而，non-parametric filter 有两个限制：它们在空间域不是局部化（localized）的、它们学习的复杂度是 $O(n)$$O(n)$（即数据的维度）。这些问题可以通过使用多项式滤波器（polynomial filter）来解决：

   $$g_{\theta }(\mathbf{\Lambda })=\sum _{k=0}^{K-1}{\theta }_k{\mathbf{\Lambda }}^k$$

   其中：参数 $\overrightarrow{\theta }=({\theta }_1,\cdots ,{\theta }_K)\in {\mathbb{R}}^K$$\vec\theta=(\theta_1,\cdots,\theta_K)\in \mathbb R^K$ 为多项式系数组成的向量。

   以顶点 $i$$i$ 为中心的滤波器 $g_{\theta }$$g_\theta$ 在顶点 $j$$j$ 上的取值为：

   $${(g_{\theta }(\mathbf{L}){\overrightarrow{\delta }}_i)}_j={(g_{\theta }(\mathbf{L}))}_{i,j}=\sum _{k=0}^{K-1}{\theta }_k{\left({\mathbf{L}}^k\right)}_{i,j}$$

   它的物理意义是：一个 delta 脉冲信号 ${\overrightarrow{\delta }}_i\in {\mathbb{R}}^n$$\mathbf{\vec \delta}_i\in \mathbb R^n$ （它在节点 $i$$i$ 上取值为一、在其它节点取值为零）经过滤波器之后，在节点 $j$$j$ 上的取值。

   根据 《Wavelets on Graphs via Spectral Graph Theory》 的引理5.2，$d_{\mathcal{G}}(i,j)>K$$d_\mathcal G(i,j)\gt K$ 意味着 ${\left({\mathbf{L}}^K\right)}_{i,j}=0$$\left(\mathbf L^K\right)_{i,j} = 0$ ，其中 $d_{\mathcal{G}}(\cdot ,\cdot )$$d_\mathcal G(\cdot,\cdot)$ 表示两个顶点之间的最短路径（即，连接图上两个顶点的最少的边数）。因此，由拉普拉斯算子的 $K$$K$ 阶多项式表示的谱滤波器（ spectral filter ）恰好是 K-localized 的。此外，它的学习复杂度为 $O(K)$$O(K)$，即滤波器的尺寸，因此与经典 CNN 的复杂度相同。

5. 快速滤波（fast filtering）的递归公式：虽然我们已经展示了如何学习具有 $K$$K$ 个参数的localized filter ，但是由于还需要与傅里叶基 $\mathbf{U}$$\mathbf U$ 相乘，因此对信号 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的滤波 $\overrightarrow{\mathbf{y}}=\mathbf{U}{g}_{\theta }(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$\mathbf{\vec y} = \mathbf Ug_\theta(\mathbf\Lambda) \mathbf U^\top \mathbf{\vec x}$ 仍然是 $O(n^2)$$O(n^2)$ 的、高昂的操作。解决这个问题的方法是将 $g_{\theta }(\mathbf{L})$$g_\theta(\mathbf L)$ 参数化为可以从 $\mathbf{L}$$\mathbf L$ 递归计算的多项式函数，因为 $K$$K$ 次地乘以一个稀疏的 $\mathbf{L}$$\mathbf L$ 矩阵的复杂度为 $O(K\times |\mathcal{E}|)\ll O(n^2)$$O(K\times|\mathcal E|)\ll O(n^2)$ 。

   一种这样的多项式是 Chebyshev 展开（传统上，它在 GSP 中被用于近似 kernel，如小波 wagelet ）。另一种选择是 Lanczos 算法，它构造了 Krylov 子空间的正交基 ${\mathcal{K}}_K(\mathbf{L},\overrightarrow{\mathbf{x}})=\text{span}\{\overrightarrow{\mathbf{x}},\mathbf{L}\overrightarrow{\mathbf{x}},\cdots ,{\mathbf{L}}^{K-1}\overrightarrow{\mathbf{x}}\}$$\mathcal K_K\left(\mathbf L,\mathbf{\vec x}\right) = \text{span}\left\{\mathbf{\vec x},\mathbf L\mathbf{\vec x},\cdots,\mathbf L^{K-1}\mathbf{\vec x}\right\}$ 。 Lanczos 算法看起来似乎有吸引力，但是它更加复杂，因此我们留待未来的工作。

   回想一下，$k$$k$ 阶切比雪夫多项式 $T_k(x)$$T_k(x)$ 可以通过递归关系来计算：

   $$\begin{array}{c}{T}_0(x)=1,T_1(x)=x\\ T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)\end{array}$$

   这些多项式构成 $L^2([-1,1],dy/\sqrt{1-y^2})$$L^2([-1,1],dy/\sqrt{1-y^2})$ 空间的一组正交基，这是关于测度 $dy/\sqrt{1-y^2}$$dy/\sqrt{1-y^2}$ 的平方可积函数的希尔伯特空间。因此，滤波器可以被参数化为：

   $$g_{\theta }(\mathbf{\Lambda })=\sum _{k=0}^{K-1}{\theta }_k{T}_k\left(\tilde{\mathbf{\Lambda }}\right)$$

   其中：

   • 参数 $\overrightarrow{\theta }\in {\mathbb{R}}^K$$\vec \theta\in \mathbb R^K$ 为切比雪夫多项式系数组成的向量。

   • $\tilde{\mathbf{\Lambda }}=2\mathbf{\Lambda }/{\lambda }_{max}-{\mathbf{I}}_n$$\tilde{\mathbf\Lambda} = 2\mathbf\Lambda/\lambda_\max - \mathbf I_n$ 为经过缩放的特征值对角矩阵，这使得它的对角线元素取值位于 [-1,+1] 之间。

   • $T_k\left(\tilde{\mathbf{\Lambda }}\right)\in {\mathbb{R}}^{n\times n}$$T_k\left(\tilde{\mathbf \Lambda}\right)\in \mathbb R^{n\times n}$ 为在 $\tilde{\mathbf{\Lambda }}$$\tilde{\mathbf \Lambda}$ 处计算的 $k$$k$ 阶切比雪夫多项式。

   滤波操作可以协作：

   $$\overrightarrow{\mathbf{y}}=g_{\theta }(\mathbf{L})\overrightarrow{\mathbf{x}}=\sum _{k=0}^{K-1}{\theta }_k{T}_k\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}$$

   其中：

   • $\tilde{\mathbf{L}}=2\mathbf{L}/{\lambda }_{max}-{\mathbf{I}}_n$$\tilde {\mathbf L} = 2\mathbf L/\lambda_\max - \mathbf I_n$ 为经过缩放的拉普拉斯矩阵。

   • $T_k\left(\tilde{\mathbf{L}}\right)\in {\mathbb{R}}^{n\times n}$$T_k\left(\tilde{\mathbf L}\right)\in \mathbb R^{n\times n}$ 为在 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ 处计算的 $k$$k$ 阶切比雪夫多项式。

   定义 ${\overline{\overrightarrow{\mathbf{x}}}}_k=T_k\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\bar{\mathbf{\vec x}}_k = T_k\left(\tilde{\mathbf L}\right) \mathbf{\vec x}\in \mathbb R^n$ ，则我们可以使用递归关系来计算：

   $$\begin{array}{c}{\overline{\overrightarrow{\mathbf{x}}}}_0=\overrightarrow{\mathbf{x}},{\overline{\overrightarrow{\mathbf{x}}}}_1=\tilde{\mathbf{L}}\overrightarrow{\mathbf{x}}\\ {\overline{\overrightarrow{\mathbf{x}}}}_k=2\tilde{\mathbf{L}}{\overline{\overrightarrow{\mathbf{x}}}}_{k-1}-{\overline{\overrightarrow{\mathbf{x}}}}_{k-2}\end{array}$$

   整个滤波操作 $\overrightarrow{\mathbf{y}}=g_{\theta }(\mathbf{L})\overrightarrow{\mathbf{x}}$$\mathbf{\vec y} = g_\theta(\mathbf L) \mathbf{\vec x}$ 需要 $O(K\times |\mathcal{E}|)$$O(K\times |\mathcal E|)$ 次操作。

6. 学习 filter：假设第 $s$$s$ 个样本的输入包含 $F_{\text{in}}$$F_\text{in}$ 个通道，第 $i$$i$ 个输入通道为信号 ${\overrightarrow{\mathbf{x}}}_{s,i}\in {\mathbb{R}}^n$$\mathbf{\vec x}_{s,i}\in \mathbb R^n$ （也称作第 $i$$i$ 个输入 feature map ） 。 第 $s$$s$ 个样本的第 $j$$j$ 个输出 feature map 为：

   $${\overrightarrow{\mathbf{y}}}_{s,j}=\sum _{i=1}^{F_{\text{in}}}{g}_{{\theta }_{i,j}}(\mathbf{L}){\overrightarrow{\mathbf{x}}}_{s,i}\in {\mathbb{R}}^n,1\le j\le F_{\text{out}}$$

   其中：${\overrightarrow{\theta }}_{i,j}\in {\mathbb{R}}^K$$\vec\theta_{i,j}\in \mathbb R^K$ 为 layer 的待训练参数。总的参数规模为 $F_{\text{in}}\times F_{\text{out}}\times K$$F_\text{in}\times F_\text{out}\times K$ 。

   假设 mini-batch 样本的损失函数为 $\mathcal{L}$$\mathcal L$ ，则为了进行反向传播我们需要计算如下的梯度：

   $$\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\theta }}_{i,j}}=\sum _{s=1}^S{[{\overline{\overrightarrow{\mathbf{x}}}}_{s,i,0},\cdots ,{\overline{\overrightarrow{\mathbf{x}}}}_{s,i,K-1}]}^{\mathrm{\top }}\frac{\partial L}{\partial {\overrightarrow{\mathbf{y}}}_{s,j}},\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{x}}}_{s,i}}=\sum _{j=1}^{F_{\text{out}}}{g}_{{\theta }_{i,j}}(\mathbf{L})\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{y}}}_{s,j}}$$

   其中：$S$$S$ 为 mini-batch size 。

   上述三种计算中的每一种都归结为 $K$$K$ 次稀疏矩阵与向量的乘法、以及一次稠密矩阵和向量的乘法，因此计算成本为 $O(K\times |\mathcal{E}|\times F_{\text{in}}\times F_{\text{out}}\times S)$$O(K\times |\mathcal E|\times F_\text{in}\times F_\text{out}\times S)$ 。这些运算可以通过张量操作在并行架构上有效地计算。

   最后，$[{\overline{\overrightarrow{\mathbf{x}}}}_{s,i,0},\cdots ,{\overline{\overrightarrow{\mathbf{x}}}}_{s,i,K-1}]$$\left[\bar{\mathbf{\vec x}}_{s,i,0},\cdots,\bar{\mathbf{\vec x}}_{s,i,K-1}\right]$ 仅需要计算一次。

1.1.2 图粗化 Graph Coarsening

1. 池化操作需要在图上有意义的邻域上进行，从而将相似的顶点聚类在一起。对多个 layer 执行池化等价于保留局部几何结构的图多尺度聚类（multi-scale clustering）。然而，众所周知，图聚类 （graph clustering ）是 NP-hard 的并且必须使用近似算法。虽然存在许多聚类算法（例如流行的谱聚类 spectral clustering），但是我们最感兴趣的还是 multi-level 聚类算法。在 multi-level 聚类算法中，每个 level 都会生成一个更粗（coarser）的图，其中这个图对应于不同分辨率看到的数据域（ data domain ）。此外，在每个 level 将图的大小减少两倍的聚类技术提供了对粗化（coarsening）和池化大小的精确控制。

2. 在这项工作中，我们利用了 Graclus multi-level 聚类算法的粗化阶段。Graclus multi-level 聚类算法已被证明在对各种图进行聚类时非常有效。图上的代数多重网格（algebraic multigrid）技术、以及 Kron reduction 是未来工作中值得探索的两种方法。

   建立在 Metis 上的 Graclus 使用贪心算法来计算给定图的连续更粗（successive coarser）的版本，并且能够最小化几个流行的谱聚类目标（spectral clustering objective）。在这些谱聚类目标中，我们选择归一化割（ the normalized cut ）。Graclus 的贪心规则为：

   • 在每个coarsening level ，选择一个未标记（unmarked）的顶点 $i$$i$ ，并选择它的一个未标记的邻居顶点 $j$$j$ ，使得最大化local normalized cut $W_{i,j}(1/d_i+1/d_j)$$W_{i,j}(1/d_i + 1/d_j)$ 。

   • 然后标记（mark）并粗化（coarsen）这对匹配的顶点 $i,j$$i,j$ ，并且所有其它顶点与这个粗化顶点的权重等于所有其它顶点和 $i,j$$i,j$ 权重之和。

   • 持续配对，直到所有顶点都被探索（这样就完成了一轮粗化）。

     这其中可能存在部分独立顶点，它不和任何其它顶点配对。

   这种粗化算法非常块，并且每轮粗化都将顶点数除以2 从而从一个 level 到下一个更粗的 level 。

1.1.3 图信号的快速池化

1. 池化操作将被执行很多次，因此该操作必须高效。粗化之后，输入图的顶点及其粗化版本没有以任何有意义的方式排列（arrange） 。因此，直接应用池化操作将需要一个 table 来存储上一个 level 的顶点与到下一个 level 的顶点（更粗化的版本）之间的对应关系。这将导致内存效率低下、读取速度慢、并且难以并行化。

   然而，我们可以排列顶点，使得图池化（graph pooling ）操作变得与一维池化一样高效。我们分为两步进行：创建一棵平衡的二叉树、重排顶点。

2. 粗化之后，每个节点要么有两个子节点（如果它是在更精细的 level 被匹配到的）；要么没有（如果它在更精细的 level 未被匹配到），此时该节点是一个 singleton，它只有一个子节点。从最粗的 level 到最细的 level，我们为每个singleton 节点添加一个 fake 节点作为子节点，这样每个节点就都有两个子节点。fake 节点都是断开（ disconnected ）的。

   这种结构是一棵平衡二叉树：一个节点要么包含两个常规子节点（如下图中的 level 1 节点 0 ），要么包含一个 singletons 子节点和一个 fake 子节点（如下图中的 level 2 节点 0） 。fake 节点总是包含两个 fake 子节点，如下图中的 level 1 节点 1。注意，下图中从上到下依次是 level 0, level 1, level 2 。

   输入信号在 fake 节点处使用 neutral value 初始化，如当使用 ReLU 激活函数时为 0 。因为这些 fake 节点是断开的，因此滤波不会影响到初始的 neutral value 。虽然这些 fake 节点确实人为地增加了维度从而增加了计算成本，但是我们发现在实践中，Graclus 留下的 singleton 节点数量非常少。

   我们在最粗（coarsest ）的 level 上任意排列节点，然后将这个次序传播到最精细（finest）的 level ，即节点 $k$$k$ 具有节点 $2k$$2k$ 和 $2k+1$$2k+1$ 作为子节点，从而在最精细的 level 产生规则的次序（regular ordering ）。规则的意思是相邻节点在较粗的 level 上层次地合并。池化如此一个重排的图信号，类似于池化一个常规的一维信号（以步长为 2 ）。

   下图显示了整个池化过程的示例。这种规则排列 （regular arrangement） 使得池化操作非常高效，并且满足并行架构（如 GPU），因为内存访问是局部的，即不需要 fetch 被匹配的节点。

   池化的本质是：对每个节点多大范围内的邻域进行池化。

   

3. 一个池化的例子如下图。带颜色的链接表示配对，红色圆圈表示未能配对顶点，蓝色圆圈表示 fake 顶点。

   考虑图 ${\mathcal{G}}_0$$\mathcal G_0$ 上定义的信号 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^8$$\mathbf{\vec x}\in \mathbb R^8$ 的最大池化，池化大小为 4 。${\mathcal{G}}_0$$\mathcal G_0$ 为原始输入，即最精细的 level ，它拥有 $n_0=|{\mathcal{V}}_0|=8$$n_0 = |\mathcal V_0| = 8$ 个顶点，以任意顺序。对于大小为 4 的池化，我们需要执行 2 次粗化操作（因为每次粗化都将顶点数除以2 ）：

   • Graclus第一次粗化产生图 ${\mathcal{G}}_1$$\mathcal G_1$ ，顶点数量 $n_1=|{\mathcal{V}}_1|=5$$n_1 = |\mathcal V_1| = 5$ 。

   • Graclus第二次粗化产生图 ${\mathcal{G}}_2$$\mathcal G_2$ ，顶点数量 $n_2=|{\mathcal{V}}_2|=3$$n_2 = |\mathcal V_2| = 3$ ，即最粗的level 。

   因此我们设置 $n_2=3,n_1=6,n_0=12$$n_2= 3, n_1=6, n_0=12$ ，并将 fake 节点（蓝色）添加到 ${\mathcal{V}}_1$$\mathcal V_1$（添加 1 个 fake 节点）、${\mathcal{V}}_0$$\mathcal V_0$（添加 4 个 fake 节点），从而与 singelton 节点（橙色）配对，这样每个节点正好有两个子节点。然后 ${\mathcal{V}}_2$$\mathcal V_2$ 中的节点被任意排序，${\mathcal{V}}_1$$\mathcal V_1$ 和 ${\mathcal{V}}_0$$\mathcal V_0$ 中的节点因此而被排序。此时，${\mathcal{V}}_0$$\mathcal V_0$ 中节点的排列允许在 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^{12}$$\mathbf{\vec x}\in \mathbb R^{12}$ 上执行一个常规的一维池化，使得：

   $$\overrightarrow{\mathbf{z}}=[max(x_0,x_1),max(x_4,x_5,x_6),max(x_8,x_9,x_{10})]\in {\mathbb{R}}^3$$

   其中信号分量 $x_2,x_3,x_7,x_{11}$$x_2,x_3,x_7,x_{11}$ 被设置为 neutral value。

   

1.2 实验

1. 我们将 non-parametric 和non-localized 的 filter 称作 Non-Param（即 $g_{\theta }(\mathbf{\Lambda })=\text{diag}\left(\overrightarrow{\theta }\right)$$g_\theta(\mathbf\Lambda) = \text{diag}\left(\vec\theta\right)$） ，将《Spectral Networks and Deep Locally Connected Networks on Graphs》中提出的 filter 称作 Spline（即 $g_{\theta }(\mathbf{\Lambda })=\mathbf{B}\theta$$g_\theta(\mathbf\Lambda) = \mathbf B\theta$），将我们提出的 filter 称作Chebyshev（即 $g_{\theta }(\mathbf{\Lambda })=\sum _{k=0}^{K-1}{\theta }_k{T}_k\left(\tilde{\mathbf{\Lambda }}\right)$$g_\theta(\mathbf\Lambda) = \sum_{k=0}^{K-1}\theta_kT_k\left(\tilde{\mathbf \Lambda}\right)$） 。

   我们总是采用 Graclus 粗化算法，而不是 《Spectral Networks and Deep Locally Connected Networks on Graphs》 中提出的简单聚集算法（agglomerative method）。我们的动机是比较学到的 filter，而不是比较粗化算法。

   我们在描述网络架构时使用以下符号：FCk 表示一个带 $k$$k$ 个神经元的全连接层，Pk 表示一个尺寸和步长为 $k$$k$ 的池化层（经典池化层或者图池化层），GCK 表示一个输出 $k$$k$ 个feature map 的图卷积层（graph convolutional layer），Ck 表示一个输出 $k$$k$ 个 feature map 的经典卷积层。

   所有的FCk,GCk,Ck 都使用ReLU 激活函数。最后一层始终是 softmax 回归。损失函数 $\mathcal{L}$$\mathcal L$ 是交叉熵损失，以及对所有 FCk 层权重的 l2 正则化。mini-batch size $S=100$$S=100$ 。

2. MNIST 实验：我们考虑将我们的方法应用于基准的 MNIST 分类数据集，它是欧氏空间的 case 。 MNIST 分类数据集包含 70000 张数字图片，每张图片是 28 x 28 的2D 网格。对于我们的图模型，我们构建了一个 2D 网格对应的8 层图神经网络，它产生了 $n=|\mathcal{V}|=976$$n=|\mathcal V|= 976$ 个节点（其中 ${28}^2=784$$28^2=784$ 个像素，以及额外的 192 个 fake 节点），以及 $|\mathcal{E}|=3198$$|\mathcal E|=3198$ 条边。遵从标准的做法，k-NN similarity graph 的权重（即人工构建的input graph 中，每条边的权重）计算为：

   $$W_{i,j}=\exp (-\frac{||{\overrightarrow{\mathbf{z}}}_i-{\overrightarrow{\mathbf{z}}}_j|{|}_2^2}{{\sigma }^2})$$

   其中 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 表示像素点 $i$$i$ 的2D 坐标。

   模型配置为（来自于 TensorFlow MNIST tutorial ）：LeNet-5-like 的网络架构，并且超参数为：dropout rate = 0.5，正则化系数为 $5\times {10}^{-4}$$5\times 10^{-4}$ ，初始学习率为0.03，学习率衰减系数 0.95，动量 0.9 。标准卷积核的尺度为 5x5，图卷积核的 $K=25$$K=25$ ，二者尺寸相同。所有模型训练 20 个 epoch 。

   本实验是我们模型的一项重要的健全性检查 （sanity check），它必须能够在任何图上抽取特征，包括常规的 2D grid 。下表显示了我们的模型与具有相同架构的经典 CNN 模型的性能非常接近。

   性能的差距可以用谱域滤波器的各向同性的特性（isotropic nature）来解释，即常规 graph 中的边不具有方向性，但是 MNIST 图片作为2D grid 具有方向性（如像素点的上下左右）。这是优势还是劣势取决于具体的问题。

   性能差距的其它解释是：我们的模型缺乏架构设计经验，以及需要研究更合适的优化策略或初始化策略。

   

3. 20NEWS 数据集的文本分类：为了验证我们的模型可应用于非结构化数据，我们将我们的技术应用于 20NEWS 数据集上的文本分类问题。20NEWS 数据集包含 18846 篇文档，分为20 个类别。我们将其中的 11314 篇文档用于训练、7532 篇文档用于测试。我们从所有文档的 93953 个单词中保留最高频的一万个单词。每篇文档使用词袋模型（bag-of-word model） 提取特征，并根据文档内单词的词频进行归一化。

   为了测试我们的模型，我们构建了16 层图神经网络，图的构建方式为：

   $$W_{i,j}=\exp (-\frac{||{\overrightarrow{\mathbf{z}}}_i-{\overrightarrow{\mathbf{z}}}_j|{|}_2^2}{{\sigma }^2})$$

   其中 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 为单词 $i$$i$ 的 word2vec embedding 。每篇文档对应一张图，它包含 $n=|\mathcal{V}|=10000$$n=|\mathcal V|=10000$ 个顶点、$|\mathcal{E}|=132834$$|\mathcal E|=132834$ 条边。

   word2vec embedding 是在当前数据集上训练的？还是在更大的、额外的数据集上训练的？论文未说明。

   所有模型都由 Adam 优化器训练 20 个 epoch，初始学习率为 0.001 。该架构是 $K=5$$K=5$ 的GC32 。结果如下图所示，在这个小数据集上，虽然我们的模型未能超越Multinomial Naive Bayes 模型，但是它超越了所有全连接神经网络模型，而这些全连接神经网络模型具有更多的参数。

   

4. 效果比较：我们在MNIST 数据集上比较了不同的图卷积神经网络架构的效果，其中 $K=25$$K=25$ 。可以看到我们的方法优于 Spline 以及需要 $O(n)$$O(n)$ 个参数的Non-Param。

   

   为了给出不同 filter 的收敛性，下图给出训练过程中这几种架构的验证集准确率、训练集损失，横轴表示迭代次数。

   

5. 效率比较：我们在 20NEWS 数据集上比较了不同网络架构的计算效率，其中 $K=25$$K=25$ 。我们模型的计算复杂度为 $O(n)$$O(n)$，而 《Spectral Networks and Deep Locally Connected Networks on Graphs》 的计算复杂度为 $O(n^2)$$O(n^2)$ 。测量的运行时间是总训练时间除以梯度更新的 step 数（即每个mini-batch 的处理时间，其中batch-size = 100 ）。

   

   我们在 MNIST 数据集上验证了不同网络架构的并行性。下表显式了从 CPU 迁移到 GPU 时，我们的方法与经典 CNN 类似的加速比。这体现了我们的模型提供的并行化机会。我们的模型仅依赖于矩阵乘法，而矩阵乘法可以通过NVIDA 的 cuBLAS 库高效的支持。

   

6. 图质量的影响：要使任何 graph CNN 成功，数据集必须满足一定条件：图数据必须满足局部性（locality）、平稳性（stationarity）、组合性（compositionality ）的统计假设。因此，学到的滤波器的质量及其分类性能关键取决于图的质量。从MNIST 实验我们可以看到：从欧式空间的网格数据中基于 kNN 构建的图，这些图数据质量很高。我们基于这些图数据采用graph CNN 几乎获得标准CNN 的性能。并且我们发现，kNN 中 k 的值对于图数据的质量影响不大。

   作为对比，我们从MNIST 中构建随机图，其中顶点之间的边是随机的。可以看到在随机图上，图卷积神经网络的准确率下降。在随机图中，数据结构发生丢失，因此卷积层提取的特征不再有意义。

   但是为什么丢失了结构信息之后，准确率还是那么高？读者猜测是有一些非结构性的因素在生效，例如某些像素点级别的特性。

   

   图像可以通过网格图来构成，但是必须人工地为 bag-of-word 表示的文档来构建 feature graph 。我们在这里研究三种表示单词 $\overrightarrow{\mathbf{z}}$$\mathbf{\vec z}$ 的方法：将每个单词表示为一个 one-hot 向量、通过 word2vec 从数据集中学习每个单词的 embedding 向量、使用预训练的单词word2vec embedding 向量。对于较大的数据集，可能需要 approximate nearest neighbor: ANN 算法（因为当图的顶点数量较大时找出每个顶点的kNN 顶点的计算复杂度太大），这就是我们在学到的 word2vec embedding 上尝试 LSHForest 的原因。下表报告了分类结果，这突出了结构良好的图的重要性。其中：bag-of-words 表示 one-hot 方法，pre-learned 表示预训练的 embedding 向量，learned 表示从数据集训练 embedding 向量，approximate 表示对 learned 得到的 embedding 向量进行最近邻搜索时使用LSHForest 近似算法，random 表示对 learned 得到的 embedding 向量采用随机生成边而不是基于 kNN 生成边。